//方法一：扩展欧几里得算法，同时这里也说明了a和p只有在互素的情况下才存在逆元,p可以不是质数。
LL exgcd(LL a,LL b,LL &x,LL &y)//扩展欧几里得算法 
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	LL ret=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return ret;
}
LL getInv(int a,int mod)//求a在mod下的逆元，不存在逆元返回-1 
{
	LL x,y;
	LL d=exgcd(a,mod,x,y);
	return d==1?(x%mod+mod)%mod:-1;
}
//方法二:费马小定理/欧拉定理//mod为素数
LL qkpow(LL a,LL p,LL mod)
{
	LL t=1,tt=a%mod;
	while(p)
	{
		if(p&1)t=t*tt%mod;
		tt=tt*tt%mod;
		p>>=1;
	}
	return t;
}
LL getInv(LL a,LL mod)
{
	return qkpow(a,mod-2,mod);
}
//方法三：递推求逆元//mod数是不大的素数
//线性
vector<long long> inv(n + 5);
inv[1] = 1;
for(int i = 2; i <= n; i ++) {
	inv[i] = (p - p / i) * inv[p % i] % p;
}
//递推
LL inv(LL i)
{
	if(i==1)return 1;
	return (mod-mod/i)*inv(mod%i)%mod;
}
a % b == 1 等价于 gcd(a,b) == 1;
a 在模 n 意义逆元不存在等价于 gcd(a,n)≠1

